정보과학회 컴퓨팅의 실제 논문지 (KIISE Transactions on Computing Practices)
Current Result Document :
| 한글제목(Korean Title) |
단조 증가 성질을 지닌 데이터 도메인에서의 집합 유사 시퀀스 매칭 방법 |
| 영문제목(English Title) |
A Set-based Similar Sequence Matching Method in Monotonically Increasing Data Domains |
| 저자(Author) |
황우성
임효상
Woosung Whang
Hyo-Sang Lim
|
| 원문수록처(Citation) |
VOL 27 NO. 03 PP. 0151 ~ 0156 (2021. 03) |
한글내용
(Korean Abstract) |
데이터 도메인이 가진 단조 증가 성질이란 시간이 흐름에 따라 도메인의 존재하는 값들이 사라지지 않고 증가하여 도메인이 확장되는 성질을 뜻한다. 본 논문에서는 단조 증가 성질을 가진 도메인에서의 효율적인 집합 유사 시퀀스 매칭 방법을 제안한다. 단조 증가 성질을 활용해 매칭 수행 시 발생하는 후보의 개수를 크게 줄이고, 매칭 수행의 시간을 감소시킨다. 제안하는 방법은 1) 단조 증가 성질을 활용하여 두 집합의 교집합 크기가 허용치 이상일 가능성을 미리 확인하고, 2) 공통 원소 존재 여부를 미리 파악하여 교집합 크기 예측의 정확도를 높임으로써 유사 시퀀스 매칭의 검색 범위를 줄여서 성능을 높일 수 있다는 장점을 가진다. 성능 평가 결과 제안하는 방법이 기존 방법에 비해 약 1.7배의 수행 시간 단축과 후보 감축을 보인다.
|
영문내용
(English Abstract) |
The monotonically increasing nature of a data domain means that the domain expands as new elements are added over time if elements already existing in the domain are never removed. In this paper, we propose an efficient set-based similar sequence matching method that uses the monotonically increasing property. Specifically, by using the monotonically increasing property, the proposed method considerably reduces the number of candidates generated during matching and reduces the processing time needed to perform the matching. The proposed method improves the similar sequence matching efficiency by reducing the search spaces for the matching as follows: 1) determining if two given sets are likely to be above the threshold by utilizing the monotonically increasing property, 2) determining if the intersection size is likely to be above the threshold with higher accuracy by checking for the existence of common elements in the two sets. According to the experimental results, we show that the proposed method reduces the processing time and the number of candidates by about 1.7 times compared to the existing method.
|
| 키워드(Keyword) |
도메인
단조 증가
집합
집합 유사도
집합 유사 시퀀스 매칭
domain
monotonically increasing
set
set similarity
set-based similar sequence matching
|
| 파일첨부 |
PDF 다운로드
|
